package leetcode;

import base.ebay.PathSum;

public class Lc74 {



    public boolean searchMatrix(int[][] matrix, int target) {
        int x = getRow(matrix, target, matrix[0].length - 1, 0, matrix.length - 1);
        int col =  getCol(matrix, target, x, 0, matrix[0].length - 1);
        return col == -1 ? false : true;
    }

    public int getCol(int[][] matrix, int target, int row, int l, int r) {
        if (l > r) {
            return -1;
        }
        int mid = (l + r) / 2;
        if (matrix[row][mid] == target) return mid;
        if (matrix[row][mid] > target)
            return getCol(matrix, target, row, l, mid - 1);
        return getCol(matrix, target, row, mid + 1, r);
    }

    //返回target所在的行，如果没有值等于target，则返回第一个大于target值的行号
    public int getRow(int[][] matrix, int target, int n, int l, int r) {
        if (l >= r) {
            return r; //r区间始终是在合理范围内
        }
        int mid = (l + r) / 2;
        if (matrix[mid][n] < target)
           return getRow(matrix, target, n, mid + 1, r);
        else if (matrix[mid][n] > target) {
           return getRow(matrix, target, n, l, mid); // 如果存在matrix[mid][n] == target就返回mid,如果不存在，就返回第一个大于target值的位置
        } else return mid;
    }
}
